package com.lw.leetcode.binary;

/**
 * 剑指 Offer 53 - II. 0～n-1中缺失的数字
 *
 * @Author liw
 * @Date 2021/5/8 17:32
 * @Version 1.0
 */
public class MissingNumber {

    public static void main(String[] args) {
        MissingNumber test = new MissingNumber();
//        int[] arr = {0,1,3};
//        int[] arr = {0,1,2,3,4,5,6,7,9};
//        int[] arr = {1,2,3,4,5,6,7};
        int[] arr = {0, 1,2,3,4,5,6,7};
        int i = test.missingNumber(arr);
        System.out.println(i);
    }

    public int missingNumber(int[] nums) {
        int st = 0;
        int end = nums.length - 1;

        while (st <= end) {
            int m = st + ((end - st) >> 1);
            if (m == nums[m]) {
                st = m + 1;
            } else {
                if (m == 0) {
                    return 0;
                }
                if (m- 1 == nums[m - 1]) {
                    return m;
                }
                end = m - 1;
            }
        }
        return end + 1;
    }
}
